The present invention relates to a secret key generating method for generating secret keys of an entity at a plurality of key generating agencies (centers), an encryption method for encrypting information so that parties other than the party concerned are prevented from knowing the content of the information, a cryptographic communication method and cryptographic communication system for performing cryptographic communication, and a memory product/data signal embodied in carrier wave for recording/transferring an operation program of this secret key generating method.
In the modern society, called a highly information-oriented society, based on a computer network, important business documents and image information are transmitted and communicated in a form of electronic information. Such electronic information cab be easily copied, so that it tends to be difficult to discriminate its copy and original from each other, thus bringing about an important issue of data integrity. In particular, it is indispensable for establishment of a highly information oriented society to implement such a computer network that meets the factors of “sharing of computer resources,” “multi-accessing,” and “globalization,” which however includes various factors contradicting the problem of data integrity among the parties concerned. In an attempt to eliminate those contradictions, encrypting technologies which have been mainly used in the past military and diplomatic fields in the human history are attracting world attention as an effective method for that purpose.
A cipher communication is defined as exchanging information in such a manner that no one other than the participants can understand the meaning of the information. In the field of the cipher communication, encryption is defined as converting an original text (plaintext) that can be understood by anyone into a text (ciphertext) that cannot be understood by the third party and decryption is defined as restoring a ciphertext into a plaintext, and cryptosystem is defined as the overall processes covering both encryption and decryption. The encrypting and decrypting processes use secret information called an encryption key and a decryption key, respectively. Since the secret decryption key is necessary in decryption, only those knowing this decryption key can decrypt ciphertexts, thus maintaining data security.
The encryption key and the decryption key may be either the same or different from each other. A cryptosystem using the same key is called a common-key cryptosystem, and DES (Data Encryption Standards) employed by the Standard Agency of the USA Commerce Ministry is a typical example. As an example of the cryptosystem using the keys different from each other, a cryptosystem called a public-key cryptosystem has been proposed. In the public-key cryptosystem, each user (entity) utilizing this cryptosystem generates a pair of encryption and decryption keys and publicizes the encryption key in a public key list, thereby keeping only the decryption key in secret. In this public-key cryptosystem, the paired encryption and decryption keys are different from each other, so that the public-key cryptosystem has a feature that the decryption key cannot be known from the encryption key with a one-way function.
The public-key cryptosystem is a breakthrough in cryptosystem which publicizes the encryption key and meets the above-mentioned three factors required for establishing highly information-oriented society, so that it has been studied actively for its application in the field of information communication technologies, thus leading RSA cryptosystem being proposed as a typical public-key cryptosystem. This RSA cryptosystem has been implemented by utilizing the difficulty of factorization into prime factors as the one-way function. Also, a variety of other public-key cryptosystems have been proposed that utilize the difficulty of solving discrete logarithm problems.
Besides, a cryptosystem has been proposed that utilizes ID (identity) information identifying individuals, such as post address and name of each entity. This cryptosystem generates an encryption/decryption key common to a sender and a receiver based on ID information. Besides, the following ID-information based cryptosystems are provided: (1) a technique which needs a preliminary communication between the sender and the receiver prior to a ciphertext communication and (2) a technique which does not need a preliminary communication between the sender and the receiver prior to a ciphertext communication. The technique (2), in particular, does not need a preliminary communication, so that its entities are very convenient in use, thus considered as a nucleus for the future cryptosystems.
A cryptosystem according to this technique (2) is called ID-NIKS (ID-based non-interactive key sharing scheme), whereby sharing an encryption key without a preliminary communication is enabled by employing ID information of a communication partner. The ID-NIKS needs not exchange a public key or a secret key between a sender and a receiver nor receive a key list or services from third parties, thus securing safe communications between any given entities.
FIG. 1 shows principles for this ID-NIKS system. This system assumes the presence of a reliable center as a key generating agency, around which a common-key generation system is configured. In FIG. 1, the information specific to an entity A, i.e. its ID information of a name, a post address, a telephone number, etc. is represented by h(IDA) using a hash function h(•). For an any given entity A, the center calculates secret information SAi as follows on the basis of center public information {Pci}, center secret information {SCi} and ID information h(IDA) of the entity A, and sends it to the entity A secretly:SAi=Fi({SCi}, {PCi}, h(IDA))
The entity A generates, for communications between itself and another arbitrary entity B, a common key KAB for encryption and decryption with its own secret {SAi}, center public information {PCi} and entity B's ID information h(IDB) of the partner entity B as follows:KAB=f({SAi}, {PCi}, h(IDB))
The entity B also generates a common key KBA for the entity A similarly. If a relationship of KAB=KBA holds true always, these keys KAB and KBA can be used as the encryption and decryption keys between the entities A and B.
In the above-mentioned public-key cryptosystem, for example, an RSA cryptosystem, its public key measures 10-fold and more as long as the presently used telephone number, thus being very troublesome. To guard against this, in the ID-NIKS, each ID information can be registered in a form of name list to thereby be referenced in generating a common key used between any given entities. Therefore, by safely implementing such an ID-NIKS system as shown in FIG. 1, a convenient cryptosystem can be installed over a computer network to which a lot of entities are subscribed. For these reasons, the ID-NIKS is expected to constitute a core of the future cryptosystem.
The ID-NIKS has the following two problems. One is that the center becomes Big Brother (the center holds the secrets of all entities and functions as a Key Escrow System). Another problem is that there is a possibility that, when a certain number of entities collude with each other, they can calculate a secret of the center. While various measures have been taken to prevent the collusion problem in terms of quantity of calculation, it is difficult to completely solve this problem.
The cause of the difficulty in solving this collusion problem is that secret parameters based on identification information (ID information) have the dual structure consisting of a center secret and a private secret. In the ID-NIKS, a cryptosystem consists of a publicized parameter of the center, publicized identification information. (ID information) of an individual and this two kinds of secret parameters, and it is necessary to design the cryptosystem so that, even when entities show each other their private secrets distributed to them, the center secret is not revealed. Thus, for the realization of such a cryptosystem, there are many problems to be solved.
Then, the present inventors have proposed a secret key generating method, an encryption method and a cryptographic communication method (hereinafter referred to as the “prior example”) based on the ID-NIKS, which can minimize the mathematical structure, avoid the collusion problem and readily construct the cryptosystem by dividing the identification information (ID information) into some blocks and distributing all secret keys based on the divided information (ID information) from a plurality of centers to an entity.
The reason why various types of cryptosystem based on the identification information (ID information) of an entity, which were proposed to solve the collusion problem, did not succeed was that the measures taken to prevent the center secret from being calculated from collusion information of the entities depended excessively on the mathematical structure. When the mathematical structure is too complicated, a method for verifying security also becomes difficult. Therefore, in the proposed method of the prior example, the identification information (ID information) of an entity is divided into some blocks and all the secret keys for the respective divided identification information (ID information) are distributed to the entity, thereby minimizing the mathematical structure.
In the prior example, a plurality of reliable centers are provided, and the centers generate secret keys having no mathematical structure and corresponding to the respective divided identification information (ID information) of each entity, and send the secret keys to each entity. Each entity generates a common key from the secret keys sent from the respective centers and the publicized identification information (ID information) of the communicating party, without preliminary communication. Therefore, a single center can never hold the secrets of all entities, and each center can never become Big Brother.
Moreover, the present inventors are pursuing their research to improve such a prior example and to construct a cryptographic communication system adopting the prior example. In such a cryptographic communication system, the security can be improved by increasing the number of the centers. It is thus supposed that a new center will frequently be added to a cryptographic communication system which is actually constructed by a certain number of centers.
Whenever a new center is caused to additionally participate in the cryptographic communication system, a new hash value must be set for each of the existing centers and the new center to construct a new overall hash function system, and thus changing of the overall system is unavoidable. In order to cope with the addition of a new center without changing the overall system, the following measures can be taken: each center publicizing its own hash function; and presetting a hash function of a sufficiently long bit length. In the former measure, however, it is not easy for each entity to incorporate a new hash function into its key sharing software. The latter measure poses a problem that, even if a hash function of a tremendously long bit length is prepared, the number of centers to be added is limited.